/*
题目: 删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

https://leetcode.cn/problems/delete-and-earn
 */
public class DeleteAndEarn {
    // 相邻问题 --- [打家劫舍]
    public int deleteAndEarn(int[] nums) {
        // 下标为 某个数, 元素值为个数
        int[] vec = new int[10001];
        int maxn = 0;
        for (int x : nums) {
            vec[x] ++;
            maxn = Math.max(maxn, x);
        }

        // 一直到最大值的点数
        int[] dp = new int[maxn + 1];
        dp[1] = vec[1];
        for (int i = 2; i <= maxn; i ++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + vec[i] * i);
        }

        return dp[maxn];
    }
}
